<?php
use Homework8\Graph as Graph;
use Homework8\Node;
use Homework8\Edge;

/* Autoload classes */
function __autoload($className) {
	$parts = explode('\\', $className);

	include end($parts) . '.php';
}

$directed = false;

$graphTraversal = new GraphTraversal($directed);
$graphTraversal->init();
class GraphTraversal {

	private $graph;
	private $visitedNumber;
	private $time;				// Global time
	private $directed;
	private $components;
	private $currentNode;
	private $nodeTimeStamps;
	private $maxNode;

	public function __construct($directed = true) {
		$this->time 			= 0;
		$this->visitedNumber 	= 0;
		$this->directed			= $directed;
		$this->components		= 0;
		$this->nodeTimeStamps	= array();
		$this->maxNode			= null;
	}

	public function init() {
		//$graph = $this->readKarate(new Graph());
		$graph = $this->readAirtport(new Graph());
		//$this->DFS($graph->getStart());		echo '<br>';
		$this->DFSIterative2($graph->getStart());
		$this->getComponentsNumber($graph);
		// Cloning seem to not working, too many references to other object inside the object itself
		//$graph1 = clone $graph;
		//$graph2 = clone $graph;
		
		//$this->BFS($graph->getStart());
		//echo '<br>Maxnode:' . $this->maxNode->getPredecessor()->getLabel(). '<br>';
		//var_dump($this->getMaxTreeLength());
		//$this->printTimeStamps();
		//echo 'Nr of visits: ' . $this->visitedNumber;
	}
	
	public function readAirtport(Graph $graph) {
		$file = fopen('usairport.txt', 'r');
		$header1 = fgets($file); $header2 = fgets($file);
		$startNodeSet = false;

		while (!feof($file)) {
			$line = fgets($file);
			list($fromLabel, $toLabel, $weight) = preg_split('/\s+/', $line);

			$from = $graph->getNode($fromLabel);
			if ($from == null) {
				$from = new Node($fromLabel);
			}
				
			$to = $graph->getNode($toLabel);
			if ($to == null) {
				$to = new Node($toLabel);
			}

			$edge = new Edge($to);
			$edge->setWeight($weight);
			
			if (!$this->directed) {
				// Add reference back; i.e. remember afterwards to compare $to and $from from the perspective of traversable node
				$edge->setFrom($from);
				$to->addEdge($edge, $this->directed);
			}
			$from->addEdge($edge, $this->directed);
			
			$graph->addNode($from)->addNode($to);

			if (!$startNodeSet && ($fromLabel == '0' || $fromLabel == '1')) {
				$graph->setStart($from);
				$startNodeSet = true;
			}
		}
		
		$this->graph = $graph;

		return $this->graph;
	}

	public function readKarate(Graph $graph) {
		$file = fopen('karate.txt', 'r');
		$header1 = fgets($file); $header2 = fgets($file);
		$startNodeSet = false;

		while (!feof($file)) {
			$line = fgets($file);
			list($fromLabel, $toLabel) = preg_split('/\s+/', $line);

			
			$from = $graph->getNode($fromLabel);
			if ($from == null) {
				$from = new Node($fromLabel);
			}
				
			$to = $graph->getNode($toLabel);
			if ($to == null) {
				$to = new Node($toLabel);
			}

			$edge = new Edge($to);
			if (!$this->directed) {
				// Add reference back; i.e. remember afterwards to compare $to and $from from the perspective of traversable node
				$edge->setFrom($from);
				$to->addEdge($edge, $this->directed);
			}
			$from->addEdge($edge, $this->directed);
			
			$graph->addNode($from)->addNode($to);

			if (!$startNodeSet && ($fromLabel == '0' || $fromLabel == '1')) {
				$graph->setStart($from);
				$startNodeSet = true;
			}
		}
		$this->graph = $graph;

		return $this->graph;
	}

	public function DFS(Node $node) {
		$this->visitedNumber++;
		$this->time = $this->time + 1;
		$node->setVisited(true)->setDiscoveredTime($this->time)->setDiscovered();
		$this->currentNode = $node;
		
		if ($this->maxNode == null) {
			$this->maxNode = $node;
		} else {
			if ($this->maxNode->getCost() < $node->getCost()) {
				$this->maxNode = $node;
			}
		}
		
		echo $node->getLabel() . ' ';
		
		$edges = $node->getEdges();
		if (count($edges) > 0) {
			usort($edges, array(get_class($this), 'compare'));
			foreach ($edges as $edge) {
				$to = $edge->getTo();
				if (!$this->directed) {
					$to = $edge->getTo($node);
				}
				
				if (!$to->isVisited()) {
					echo $to->getLabel() . '<br>';
					
					$to->setCost($node->getCost() + $edge->getWeight());
					$to->setPredecessor($node);
					$this->DFS($to);
				}
			}
			
	
			
			$this->time = $this->time + 1;
			
			$node->setExplored();
			$node->setExploredTime($this->time);
			$this->nodeTimeStamps[$node->getLabel()] = array(
				'd' => $node->getDiscoveredTime(),
				'e' => $node->getExploredTime(),
				'parent' => ($node->getPredecessor() != null) ? $node->getPredecessor()->getLabel() : '-1'
			);
		}
	}
	
public function SearchMaxTree(Node $node) {
	
	$file = fopen('result.txt', 'w+');
	//fwrite($file, "From\tTo\tCost\tEdge weight" . PHP_EOL);
	$stack = array();		
	array_push($stack, $node);
	
	while (count($stack) > 0) {
		$node = array_pop($stack);
		$this->currentNode = $node;
		if (!$node->isDiscovered()) {
			
			if ($this->maxNode == null) {
				$this->maxNode = $node;
			} else {
				if ($this->maxNode->getCost() < $node->getCost()) {
					$this->maxNode = $node;
				}
			}
			$node->setDiscovered();
			//echo $node->getLabel() . ' ';
			$this->visitedNumber++;
			$edges = $node->getEdges();
			if (count($edges) > 0) {
				usort($edges, array(get_class($this), 'compare3')); // sorts from largest to smallest weight
				foreach ($edges as $edge) {
					$to = $edge->getTo();
					if (!$this->directed) {
						$to = $edge->getTo($node);
					}
					
					
					if (!$to->isDiscovered()) {
						$weight = $node->getCost() + $edge->getWeight();
						//echo $node->getLabel() . "\t" . $to->getLabel() . "\t" . $weight . "\t" . $edge->getWeight() . '<br>';
						//fwrite($file, $node->getLabel() . "\t" . $to->getLabel() . "\t" . $weight . "\t" . $edge->getWeight() . PHP_EOL);
						$to->setCost($node->getCost() + $edge->getWeight());
						$to->setPredecessor($node);
					}

					array_push($stack, $to);
				}
			}
		}
	}
	
	//fclose($file);
}

	public function BFS(Node $node) {
		$queue = array();
		array_push($queue, $node);
		$node->setVisited(true);
		while (count($queue) > 0) {
			$this->visitedNumber++;
			$node = array_shift($queue);
			
			if ($this->maxNode == null) {
				$this->maxNode = $node;
			} else {
				if ($this->maxNode->getCost() < $node->getCost()) {
					$this->maxNode = $node;
				}
			}
			$this->currentNode = $node;
			
			$edges = $node->getEdges();
				
			if (count($edges) > 0) {
				var_dump($edges);
				
				usort($edges, array(get_class($this), 'compare'));
	
				foreach ($edges as $edge) {
					$to = $edge->getTo();
					if (!$this->directed) {
						$to = $edge->getTo($node);
					}
						
					if (!$to->isVisited()) {
						echo $node->getLabel() . ' ' . $to->getLabel() . '<br>';
						$to->setCost($node->getCost() + $edge->getWeight());
						$to->setPredecessor($node);
						$to->setVisited(true);
						array_push($queue, $to);
					}
				}
			}
		}
	}
	
public function randomSearch(Node $node) {
	$queue = array();
	array_push($queue, $node);
	
	while (count($queue) > 0) {
		$node = array_pop($queue);
		$this->currentNode = $node;
		
		if ($this->maxNode == null) {
			$this->maxNode = $node;
		} else {
			if ($this->maxNode->getCost() < $node->getCost()) {
				$this->maxNode = $node;
			}
		}
		
		
		$node->setVisited();			
		$this->visitedNumber++;
		$edges = $node->getEdges();
		if (count($edges) > 0) {
			shuffle($edges); 		//randomise		
			
			foreach ($edges as $edge) {
				$to = $edge->getTo();
				if (!$this->directed) {
					$to = $edge->getTo($node);
				}
				
				if (!$to->isVisited()) {
					echo $node->getLabel() . ' ' . $to->getLabel() . '<br>';
					$to->setCost($node->getCost() + $edge->getWeight());
					$to->setPredecessor($node);
					$to->setVisited(true);
					array_push($queue, $to);
				}
			}
		}
	}
}
	
	public function DFSIterative2(Node $node) {
		$stack = array();		
		array_push($stack, $node);
		
		while (count($stack) > 0) {
			$node = array_pop($stack);
			$this->currentNode = $node;
			if (!$node->isDiscovered()) {
				$node->setDiscovered();
				$node->setVisited();
			//	echo $node->getLabel() . ' ';
				$this->visitedNumber++;
				$edges = $node->getEdges();
				if (count($edges) > 0) {
					usort($edges, array(get_class($this), 'compare2'));		// reverse order for stack			
					foreach ($edges as $edge) {
						$to = $edge->getTo();
						if (!$this->directed) {
							$to = $edge->getTo($node);
						}
						
						array_push($stack, $to);
					}
				}
			}
		}
	}
	
	public function DFSIterative(Node $node) {
		$stack = array();
		
		$node->setDiscovered();
		echo $node->getLabel() . ' ';
		array_push($stack, $node);
		
		while (count($stack) > 0) {
			$node = $stack[count($stack)-1]; 	// Take the top element
			$edges = $node->getEdges();
			
			$adjacentExplored = false;
			
			if (count($edges) > 0) {				
				foreach ($edges as $edge) {
					$to = $edge->getTo();
					if (!$this->directed) {
						$to = $edge->getTo($node);
					}
									
					if (!$to->isExplored() && !$to->isDiscovered()) {
						echo $to->getLabel() . ' ';
						$to->setDiscovered();
						array_push($stack, $to);
						$adjacentExplored = true;
						break;
					}
				}
			}
			
					
			if (!$adjacentExplored && $node->isDiscovered()) {
				$node->setExplored();
				array_pop($stack);
			}
		}
	}

	
	// needs to be verified.. incorrect, counts visited nodes, not reachable nodes?
	public function getComponentsNumber(Graph $graph) {
		$start = $graph->getStart();
		$componentsNumber = 0;
		
		while ($start != null) {
			$componentsNumber++;
			echo 'Component' . $componentsNumber .':<br>';
			$this->DFSIterative2($start);
			//die();
			$start = $graph->getFirstNotVisitedNode();
		}
		
		//return $componentsNumber;
	}

	public function compare($a, $b) {
		$aLabel = $a->getTo()->getLabel();
		$bLabel = $b->getTo()->getLabel();
		if (!$this->directed) {
			
			if ($this->currentNode == $b->getTo()) {
				$bLabel = $b->getFrom()->getLabel();
			}
			
			if ($this->currentNode == $a->getTo()) {
				$aLabel = $a->getFrom()->getLabel();
			}
		}
		
		
		return ((int)$bLabel < (int)$aLabel) ? 1 : -1;
	}
	
	public function compare2($a, $b) {
		$aLabel = $a->getTo()->getLabel();
		$bLabel = $b->getTo()->getLabel();
		if (!$this->directed) {
			
			if ($this->currentNode == $b->getTo()) {
				$bLabel = $b->getFrom()->getLabel();
			}
			
			if ($this->currentNode == $a->getTo()) {
				$aLabel = $a->getFrom()->getLabel();
			}
		}
		
		
		return ((int)$bLabel >= (int)$aLabel) ? 1 : -1;
	}
	
	public function compare3($a, $b) {
		$weight1 = $a->getWeight();
		$weight2 = $b->getWeight();

		return ($weight1 < $weight2) ? 1 : -1;
	}
	
	protected function printTimeStamps() {
		ksort($this->nodeTimeStamps);
		foreach ($this->nodeTimeStamps as $label => $data) {
			echo $label . ': ' . $data['d'] . '/' . $data['e'] . ' ' . $data['parent'] . '<br>';
		}
	}
	
	protected function getMaxTreeLength() {
		
	
		$length = 0;
		$path = array();
		
		if ($this->maxNode != null) {
			$node = $this->maxNode;
			while ($node->getPredecessor() != null) {
				$path[] = $node->getLabel();
				$node = $node->getPredecessor();
				$length++;
			}
			$path[] = $node->getLabel();
		}

		$path = array_reverse($path);
		
		echo '<br>' . implode(' ', $path) . '<br>';
		
		return $length;
	}
}


